The present disclosure is related generally to generation of a polygonal mesh, and related more specifically to large scale polygonal meshes that can be generated as piecewise partitions.
Measurements taken with respect to natural phenomena often generate a significant number of data points that can sometimes be analyzed as a polygonal mesh. Typically, the data points are obtained in the form of a point cloud, which is a set of points in two dimensional or three dimensional space. The data point in the point cloud can be regularly spaced, or irregular in their spacing, and can be arbitrary in number. For example, the number of data points in a point cloud is not particularly limited, nor are there any typical constraints on the density of the data points in any given region of the point cloud. A point cloud may typically include several billion data points, for example, which can be generated by an arbitrary sensor system, such as by recording measurement samples of a given surface or shape.
Given a particular point cloud, a polygonal mesh can be generated that defines a number of polygonal shapes connecting the points. The points are typically stored in a computer memory for creation of the mesh, and are representative of specific locations in a space that is defined on one or more dimensions. Accordingly, the points represent information about characteristics of the space, and can therefore be used to define a mesh for the space.
Mesh generation algorithms have been used to connect points in a given space to obtain a mesh that can be useful for analysis of the characteristics of the space in relation to the points. However, conventional mesh generation algorithms tend to be limited in the number of points that can be practically processed to generate a mesh, since the algorithms work on all the available points or polygonal shapes generated from the points to generate a mesh. It is impractical to employ such algorithms on large data sets that have relatively large numbers of points.